public class Solver {

	private BoardNode boardNode, boardNodeTwin;

	private class BoardNode implements Comparable<BoardNode> {
		private Board board;
		private int moves;
		public BoardNode prev;
		
		public BoardNode(Board board, int moves) {
			this.board = board;
			this.moves = moves;
			prev = null;
		}
		
		public boolean isGoal() {
			return board.isGoal();
		}
		
		public Board boardCopy() {
			return board;
		}
		
		public Iterable<Board> neighbors() {
			return board.neighbors();
		}
		
		public int value() {
			return board.manhattan() + moves;
		}
		
		public int compareTo(BoardNode b2) {
			return value() - b2.value();
		}
	}
	
    public Solver(Board initial) {           // find a solution to the initial board (using the A* algorithm)
    	int moves = 0;
    	
    	boardNode = new BoardNode(initial, moves);
    	boardNodeTwin = new BoardNode(initial.twin(), moves);
    	
    	MinPQ<BoardNode> boardQueue = new MinPQ<BoardNode>();
    	boardQueue.insert(boardNode);
    	boardQueue.insert(boardNodeTwin);
    	
    	boardNode = boardQueue.delMin();
    	
    	while (!boardNode.isGoal()) {
    		
        	Stack<Board> neighbors = new Stack<Board>(); 
    		for (Board b: boardNode.neighbors())
    			neighbors.push(b);
    		
   			moves = boardNode.moves + 1;
    		
    		for (Board b: neighbors) {
    			Board bPrevious = null;
    			
    			if (boardNode.prev != null)
    				bPrevious = boardNode.prev.boardCopy();
    			
    			if (!b.equals(bPrevious)) {
	    			BoardNode node = new BoardNode(b, moves);
	    			node.prev = boardNode;
	    			boardQueue.insert(node);
    			}
    		}

    		boardNode = boardQueue.delMin();
    	}

    }
    
    public boolean isSolvable() {             // is the initial board solvable?
    	
    	BoardNode firstNode = boardNode;
    	
    	while (firstNode.prev != null)
    		firstNode = firstNode.prev;
    	
    	if (firstNode.boardCopy().equals(boardNodeTwin.boardCopy()))
    		return false;
    	
    	return true;
    }
    
    public int moves() {                     // min number of moves to solve initial board; -1 if no solution
    	if (!isSolvable())
    		return -1;
    	else
    		return boardNode.moves;
    }
    
    public Iterable<Board> solution() {      // sequence of boards in a shortest solution; null if no solution
    	BoardNode solutionNode = boardNode;
    	
    	if (isSolvable()) {
    		Stack<Board> solutionStack = new Stack<Board>();
    		
    		solutionStack.push(solutionNode.boardCopy());
    		while (solutionNode.prev != null) {
    			solutionNode = solutionNode.prev;
    			solutionStack.push(solutionNode.boardCopy());
    		}
    		
    		return solutionStack;
    	}
		else
			return null;
    }
    
    public static void main(String[] args) {  // solve a slider puzzle (given below)

    	 // create initial board from file
        In in = new In(args[0]);
        int N = in.readInt();
        int[][] blocks = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);

        // solve the puzzle
        Solver solver = new Solver(initial);

        // print solution to standard output
        if (!solver.isSolvable())
            StdOut.println("No solution possible");
        else {
            StdOut.println("Minimum number of moves = " + solver.moves());
            for (Board board : solver.solution())
                StdOut.println(board);
        }
    }
}